package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 全排列
 * @date 2025/3/11 21:56
 */
public class Permute_46 {

    public static void main(String[] args) {
        Permute_46 permute46 = new Permute_46();
        int[] nums = new int[]{1, 2, 3};
        permute46.permute(nums);
        res.forEach(System.out::println);

        System.out.println("---");
        List<List<Integer>> res = permute46.permute2(nums);
        res.forEach(System.out::println);

        System.out.println("---");
        permute46.permute3(nums).forEach(System.out::println);

        System.out.println("---");
        permute46.permute4(nums).forEach(System.out::println);
    }

    /**
     * 个解：递归回溯
     * <p>
     * 分析：
     * 1.全排列，即元素相同，但顺序不同，也属于一个新的目标结果；
     * 2.每个元素都要再次判断是否使用，通过used[]
     * 3.为什么不需要startIndex？
     */
    private List<List<Integer>> ans4 = new ArrayList<>();
    private List<Integer> path4 = new ArrayList<>();
    private int[] used4;

    public List<List<Integer>> permute4(int[] nums) {
        // nums元素不重复，每个元素只能使用一次
        // 元素相同，但顺序不同，也属于一个新的目标结果

        // 1.返回值void；入参：nums、ans、path、used
        // used记录当前元素是否使用过
        // 2.递归终止条件
        // 当path.size()==nums.length时，记录path，并结束本层讯息
        // 3.搜索过程，for循环横向遍历
        // 3.1.判断元素是否使用过，若使用过结束本层for循环
        // 3.2.记录元素值，记录使用状况；
        // 3.3.向下递归
        // 3.4.回溯；元素值和使用状况

        if (nums.length == 0) return ans4;

        used4 = new int[nums.length];
        backtrack4(nums);

        return ans4;
    }

    public void backtrack4(int[] nums) {
        if (path4.size() == nums.length) {
            ans4.add(new ArrayList<>(path4));
            return;
        }

        // 横向遍历
        for (int i = 0; i < nums.length; i++) {
            // 同一树枝，used[i]=1表示使用过，则跳过该元素
            if (used4[i] == 1) continue;

            // 记录
            path4.add(nums[i]);
            used4[i] = 1;

            // 向下递归
            backtrack4(nums);

            // 回溯
            path4.remove(path4.size() - 1);
            used4[i] = 0;
        }
    }

    /**
     * 个解：参考dmsxl-回溯
     * <p>
     * 为什么递归时，每层for循环都从0开始，而不是指定的下标？<br/>
     * ——因为本题是找排列，而排列中元素顺序不同，也是不同的排列，所以可重复使用元素。
     */
    List<List<Integer>> ans3 = new ArrayList<>();

    List<Integer> path3 = new ArrayList<>();

    // 0-未使用，1-已使用
    int[] used3;

    public List<List<Integer>> permute3(int[] nums) {
        used3 = new int[nums.length];

        backtrack3(nums);
        return ans3;
    }

    public void backtrack3(int[] nums) {
        // path3数量和nums相同，表明找到一个目标排列，直接记录
        if (path3.size() == nums.length) {
            ans3.add(new ArrayList<>(path3));
            return;
        }

        // 横向遍历
        for (int i = 0; i < nums.length; i++) {
            // 同一层级中使用过的元素，不再次使用
            if (used3[i] == 1) continue;

            // 未使用过，则记录
            path3.add(nums[i]);
            used3[i] = 1;

            // 下层递归
            backtrack3(nums);

            // 回溯
            path3.remove(path3.size() - 1);
            used3[i] = 0;
        }
    }

    /**
     * 回溯法；
     * 个人解法，参考dmsxl
     */
    public List<List<Integer>> permute2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> pathList = new ArrayList<>();
        int[] used = new int[nums.length];

        backTrack2(nums, used, pathList, result);
        return result;
    }

    public List<Integer> backTrack2(int[] nums, int[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return path;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i] == 1) continue;
            // 记录已使用的元素
            used[i] = 1;
            path.add(nums[i]);
            // 递归
            backTrack2(nums, used, path, res);
            // 回溯
            used[i] = 0;
            path.remove(path.size() - 1);
        }
        // 每层纵向遍历完后，也要返回上一层，从而进行回溯的操作
        return path;
    }

    /**
     * dmsxl解法：回溯法
     * <p>
     * 时间复杂度：T(n)=O(n!)；
     * <p>
     * 其中 n 为序列的长度，backtrack 的调用次数是 O(n!) ，而对于 backtrack 调用的每个叶结点共 n! 个；
     * <p>
     * 即横向遍历+纵向递归，遍历n个元素，每个元素递归深度n。
     * <p>
     * 空间复杂度：S(n)=O(n);
     * <p>
     * 其中 n 为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)。
     */
    private static List<List<Integer>> res = new ArrayList<>();
    private static List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int[] used = new int[nums.length];
        backTrack(nums, used);
        return res;
    }

    public void backTrack(int[] nums, int[] used) {
        // 1.确定递归的入参和返回值
        // used记录已经使用的元素，0-未使用，1-已使用

        // 2.确定终止条件
        // 当找到一个全排列集合时，path.size() == nums.length
        if (path.size() == nums.length) {
            // 记录新list，避免全局变量path回溯到最后把所有元素删除完
            res.add(new ArrayList<>(path));
            return;
        }

        // 3.单层递归逻辑：挨个取数——>回溯；
        // 遍历nums，每层递归记录一个数并记录其使用情况；递归处理下一层；回溯
        for (int i = 0; i < nums.length; i++) {
            // 不重复取数
            if (used[i] == 1) {
                continue;
            }
            // 取数
            used[i] = 1;
            path.add(nums[i]);
            // 递归
            backTrack(nums, used);

            // 回溯
            used[i] = 0;
            path.remove(path.size() - 1);
        }
    }

}
